package com.example.daiyinuo.leetcode;

import java.util.Arrays;

/**
 * //一条包含字母A-Z的消息通过以下映射进行了编码：'A' -> 1 2 'B' -> 2 3 ... 4 'Z' -> 26
 *     //要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多 种方法）。
 *     // 例如，"11106"可以映射为： "AA JF"，将消息分组为(1 1 10 6) "K JF"，
 *     // 将消息分组为(11 10 6) 注意，消息不能分组为(1 11 06)，
 *     // 因为"06"不能映射为"F"，这是由于"6"和"06"在 映射中并不等价。
 */
public class leetCode91 {

    //分析：这里每一个数字只要不是0都会对应一个字符，
    // 如果是两个数字的话必须小于等于26才能对应一个字符（并且不能有前导0）。
    // 所以这题的解题思路就有了，就是把字符串不停的拆开，要么拆一个要么拆两个，所以大家很容易想到的就是二叉树

    //我们把它看做遍历一颗二叉树，index表示访问字符的位置
    private int binaryTreeTraversal(char[] chars, int length, int index) {
//递归的终止条件，到叶子节点了，所有的字符都遍历完了，
//说明找到了一种解码的方法，直接返回1
        if (index >= length)
            return 1;
//单个0是不能构成字符的，要跳过，但两个数字的比如10，20是可以构成字符的，
//两个数字的在上一步就已经截取了。
        if (chars[index] == '0')
            return 0;
//上面类似于二叉树遍历终止条件的判断，下面类似于遍历二叉树的两个分支
//截取一个数字的分支（类似于二叉树的左分支）
//截取 个数字的分支（类似于二叉树的左分支）
        int res = binaryTreeTraversal(chars, length, index + 1);
//截取两个数字的分支（类似于二叉树的右分支），截取两个数字
//必须要小于等于26，所以这个需要判断一下
        if (index < length - 1 && (chars[index] == '1'
                || (chars[index] == '2' && chars[index + 1] <= '6')))
            res += binaryTreeTraversal(chars, length, index + 2);
        return res;
    }

    public static int numDecodings(String s) {
//使用一个map存储
        int[] map = new int[s.length()];
//默认值赋值为-1
        Arrays.fill(map, -1);
        return binaryTreeTraversal(s.toCharArray(), s.length(), map, 0);
    }

    private static int binaryTreeTraversal(char[] chars, int length, int[] map, int index) {
        if (index >= length)
            return 1;
        if (map[index] != -1)
            return map[index];
        if (chars[index] == '0')
            return 0;
        int res = binaryTreeTraversal(chars, length, map,index + 1);

        if (index < length - 1 && (chars[index] == '1'
                || (chars[index] == '2' && chars[index + 1] <= '6')))
            res += binaryTreeTraversal(chars, length, map,index + 2);
        map[index] = res;
        return res;
    }

    public static void main(String[] args) {
        //System.out.println(numDecodings("13205"));
        System.out.println(numDecodings2("13205"));
    }

    /**
     * 动态规划法解决
     * 定义dp[i]表示前i个字符的解码数。
     * dp[i]=dp[i -1]+dp[i -2]
     */
    public static int numDecodings2(String s){
        int length = s.length();
        int [] dp = new int [length+1];
        dp[0] =1;
        for(int i =1;i<=length;i++){
            //判断截取一个是否符合（只要不是0，都符合）
            if(s.charAt(i-1) != '0'){
                dp[i] +=dp[i-1];
            }
            //判断截取两个是否符合
            if(i>=2 && (s.charAt(i-2)=='1'
                    || s.charAt(i-2)=='2' && s.charAt(i-1)<='6')){
                dp[i]+=dp[i-2];
            }
        }


        return dp[length];
    }
}
